/**
 * 面试题46：把数字翻译成字符串
 */
public class Offer_46 {
    /**
     * 动态规划
     * 记 num 第 i 位数字为 x(i)
     * 
     * 状态定义：dp[i] 表示以 x(i) 结尾的数字的翻译方案数量
     * 
     * 转移方程：
     *   + 若 x(i) 和 x(i-1) 组成的两位数字可以被翻译，则 dp[i] = dp[i - 1] + dp[i - 2]；
     *   + 否则 dp[i] = dp[i - 1]。
     *   即：
     *     dp[i] = dp[i - 1] + dp[i - 2] , 10 * x(i - 1) + x(i) ∈ [10,25]
     *     dp[i] = dp[i - 1]             , 10 * x(i - 1) + x(i) ∈ [0,10)∪(25,99]
     * 
     * 初始状态：dp[0] = dp[1] = 1，即 ”无数字“ 和 ”第1位数字“ 的翻译方法都是1种。
     */
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int len = str.length();
        // 由于 dp[i] 只与 dp[i - 1] 有关
        // 因此使用两个变量 a, b 分别记录 dp[i], dp[i - 1]
        // 两个变量交替前进，可节省 dp 列表使用的 O(N) 额外空间
        int a = 1, b = 1;
        for (int i = 2; i <= len; i++) {
            String temp = str.substring(i - 2, i);
            int c = (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) ? (a + b) : a;
            b = a;
            a = c;
        }
        return a;
    }

    public int translateNum1(int num) {
        String str = String.valueOf(num);
        int len = str.length();
        int[] dp = new int[len + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= len; i++) {
            String temp = str.substring(i - 2, i);
            if (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[len];
    }

    public static void main(String[] args) {
        Offer_46 solution = new Offer_46();
        int ans = solution.translateNum(12258);
        System.out.println(ans);
    }
}
